import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class main {
    class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            if(root == null) {
                return list;
            }
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            TreeNode prev = null;

            while(cur != null || !stack.isEmpty()) {
                while(cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                TreeNode top = stack.peek();
                if(top.right == null || top.right == prev) {
                    list.add(top.val);
                    stack.pop();
                    prev = top;
                }else {
                    cur = top.right;
                }
            }
            return list;
        }
    }
    public static void main(String[] args) {
        
    }
}
